package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-10-03
 * 种花问题
 */
public class CanPlaceFlowers {

    /**
     * 主
     * 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
     * \
     * 输入：flowerbed = [1,0,0,0,1], n = 1
     * 输出：true
     * \
     * 输入：flowerbed = [1,0,0,0,1], n = 2
     * 输出：false
     *
     * @param args args
     */
    public static void main(String[] args) {
        CanPlaceFlowers canPlaceFlowers = new CanPlaceFlowers();
        int[] flowerbed = new int[]{1, 0, 0, 0, 1};
        int n = 1;
        System.out.println(canPlaceFlowers.canPlaceFlowers2(flowerbed, n));
    }

    /**
     * 可以放置鲜花:模拟
     *
     * @param flowerbed 花坛
     * @param n         n
     * @return boolean
     */
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            //统计0-0-0 这种位置可种植的数量
            if ((i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) && flowerbed[i] == 0) {
                count++;
                flowerbed[i] = 1;
            }
        }
        return count >= n;
    }

    /**
     * 贪心
     *
     * @param flowerbed 花坛
     * @param n         n
     * @return boolean
     */
    public boolean canPlaceFlowers2(int[] flowerbed, int n) {
        int count = 0;
        int len = flowerbed.length;
        //表示上一个已经种植花的位置，初始值为 -1 是因为数组的第一个位置之前没有已经种植的花。
        int prev = -1;
        for (int i = 0; i < len; i++) {
            if(flowerbed[i] == 1){
                if(prev == 0){
                    //上一个花之前的空闲位置可以种植花
                    count += i /2;
                }else{
                    //上一个花和当前花之间的空闲位置可以种植花
                    count += (i - prev - 2) / 2;
                }
                //当前位置已经种植了花
                prev = i;
            }
        }
        //计算两端是否可以种花
        //数组开头没有已经种植的花
        if (prev < 0) {
            //数组开头的空闲位置可以种植花
            count += (len + 1) / 2;
        } else {
            //数组结尾的空闲位置可以种植花
            count += (len - prev - 1) / 2;
        }
        return count >= n;
    }

}
